package leetcode.day_2021_03_8_2021_03_14;

/**
 * 53. 最大子序和
 * https://leetcode-cn.com/problems/maximum-subarray/
 */
public class LeetCode0053 {

    public static int maxSubArray(int[] nums) {
        int front = nums[0];
        int max = front;
        for (int i=1; i<nums.length; i++) {
            if (nums[i] + front < nums[i]) {
                front = nums[i];
            } else {
                front = nums[i] + front;
            }
            if (front > max) max = front;
        }
        return max;
    }

    public static void main(String[] args) {
        System.out.println(maxSubArray(new int[]{-2,1,-3,4,-1,2,1,-5,4}));
    }
}
